#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap(string &str, int i, int j)
{
    char tmp;
    tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
}

//input str must be sort before calling this function
void generatePermutation(string &str, int index, vector<string> &ans)
{
    if (index == str.size()) {
        ans.push_back(str); 
        return;
    }
    char last;
    for (int i = index; i < str.size(); i++) {
       if (i != index && str[i] == last) continue; 
       last = str[i];
       swap(str, index, i);
       generatePermutation(str, index+1, ans);
       swap(str, index, i);
    }
}


int main(int argc, char **argv)
{
    string input; 
    vector<string> ans; 
    cout << "-----------------Test 2--------------------" << endl;
    input = "abc";
    generatePermutation(input, 0, ans); 
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " ";
    cout << endl;
    cout << "-----------------Test 3--------------------" << endl;
    ans.clear();
    input = "abcb";
    generatePermutation(input, 0, ans); 
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " ";
    cout << endl;


    cout << "-----------------Test 4--------------------" << endl;
    ans.clear();
    input = "abbc";
    generatePermutation(input, 0, ans); 
    for (int i = 0; i < ans.size(); i++) 
        cout << ans[i] << " ";
    cout << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
